package 题目集.并查集;

import org.junit.Test;

/**
 * 有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
 * 一块砖直接连接到网格的顶部，或者
 * 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
 * 给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。
 * 返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
 * 注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
 * https://leetcode.cn/problems/bricks-falling-when-hit/description/
 */
public class 打砖块_逆序并查集 {
    int n, m;    //总行和总列

    /**
     * 逆序思维，先把所有hits的砖块打碎，然后逆序合并，最后逆序还原。合并的过程中，如果增加了稳定块，就记录下来。
     */
    public int[] hitBricks(int[][] grid, int[][] hits) {
        n = grid.length;
        m = grid[0].length;
        int size = n * m;
        parent = new int[size + 1];   //多加一个位置存储房顶
        this.size = new int[size + 1];    //多加一个位置存储房顶
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            this.size[i] = 1;
        }
        this.size[size] = size;     //让房顶的size变为最大，这样就不会被合并

        for (int[] hit : hits) {    //击碎
            int x = hit[0];
            int y = hit[1];
            if (grid[x][y] == 1) {
                grid[x][y] = 2;
            }
        }

        //合并顶部
        for (int i = 0; i < m; i++) {
            if (grid[0][i] == 1) {
                union(i, size);
            }
        }
        //合并其他
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    for (int[] dir : dirs) {       //这里可以剩下两次循环，但我懒
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                            union(hash(i, j), hash(x, y));
                        }
                    }
                }
            }
        }

        int[] res = new int[hits.length];
        int preSize = rootSize();
        //逆序还原
        for (int i = hits.length - 1; i >= 0; i--) {
            if (grid[hits[i][0]][hits[i][1]] != 2) continue;
            if (hits[i][0] == 0) {  //如果是顶部，先和屋顶连接
                union(hits[i][1], size);
            }
            grid[hits[i][0]][hits[i][1]] = 1;   //还原
            int cur = hash(hits[i][0], hits[i][1]);
            for (int[] dir : dirs) {
                int x = hits[i][0] + dir[0];
                int y = hits[i][1] + dir[1];
                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                    union(cur, hash(x, y));
                }
            }
            int curSize = rootSize();
            if (curSize > preSize) {    //屋顶屋顶块数量增加了
                res[i] = curSize - preSize - 1;     //减去自己
                preSize = curSize;
            }
        }
        return res;
    }

    static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};


    public int hash(int row, int col) {
        return row * m + col;
    }

    public int rootSize() {
        return size[size.length - 1];
    }

    int[] parent;
    int[] size;

    /**
     * 合并o1和o2是否会增加新的稳定块。
     * 如果会，则返回新增稳定块的数量。
     */
    public int union(int o1, int o2) {
        o1 = find(o1);
        o2 = find(o2);
        if (o1 == o2) return 0;
        if (size[o1] > size[o2]) {
            parent[o2] = o1;
            size[o1] += size[o2];
        } else {
            parent[o1] = o2;
            size[o2] += size[o1];
        }
        return 0;
    }

    public int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    @Test
    public void test() {
        int[][] grid = {{1, 0, 1}, {1, 1, 1}};
        int[][] hits = {{0, 0}, {0, 2}, {1, 1}};
        int[] res = hitBricks(grid, hits);
        for (int re : res) {
            System.out.println(re);
        }
    }
}
